package 动态规划.背包And分组And切割问题系列;

import org.junit.Test;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/6/1 8:26
 */
public class lc2698求一个数的惩罚数 {


    public int solution(int n) {
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            String s = String.valueOf(i * i);
            ans += function(0, s, i) ? i * i : 0;
        }
        return ans;
    }
    private boolean function(int index, String s, int i) {
        if (index == s.length() && i == 0) {
            return true;
        }
        //增加一个 basecase 也可以
        boolean ans = false;
        for (int j = index + 1; j <= s.length(); j++) {
            int temp = Integer.valueOf(s.substring(index, j));
            /*
             因为 数据量的范围， 所以下面 这点是 可以 剪枝的， 但是 剪枝的效果 ，并不明显！
             */
            if(i - temp < 0 || j - index > 4){
                break;
            }
            // 找到一个 满足的就可以，而不是 求个数
             if(function(j, s, i - temp)){
                 return true;
             }
        }
        return ans;
    }
    /*

     从 arignote 的代码中学到了很多的东西！
     首先是这个basecase 这里， arignote 写的是 非常的 正确的， 对于 把必须要走到 末尾的来说
     说实话，好像都差不多， 要注意  basecase 非常的关键！

     */
    public int punishmentNumber(int n) {
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            sum += punishmentNumber(0, "" + i * i, i) ? i * i : 0;
        }
        return sum;
    }

    private boolean punishmentNumber(int i, String s, int n) {
        if (i == s.length()) {
            return n == 0;
        }
        for (int j = i + 1; j <= s.length(); j++) {
            if (punishmentNumber(j, s, n - Integer.parseInt(s.substring(i, j)))) {
                return true;
            }
        }
        return false;
    }
}
